/**
 * 
 */
package zhoujian.oj.leetcode;

/*
 * You are given two linked lists representing two non-negative numbers. 
 * The digits are stored in reverse order and each of their nodes contain a single digit. 
 * Add the two numbers and return it as a linked list.
 * 
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * 
 */

/**
 * @author hyper
 * @email zjkermit@gmail.com
 * @date Dec 12, 2013
 * @version 1.0
 * @description 
 */
public class AddTwoNumbers {
	
	public class ListNode {
		int val;
		ListNode next;
		ListNode(int x) {
			val = x;
			next = null;
		}
	}
	
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		int carry = 0;
		ListNode lr = l1;
		ListNode pre = l1;
		
		if (l1 == null) {
			return l2;
		}
		
		if (l2 == null) {
			return l1;
		}
		
		while (l1 != null) {
			if (l2 != null) {
				int temp = l1.val + l2.val + carry;
				if (temp > 9) {
					temp -= 10;
					carry = 1;
				} else {
					carry = 0;
				}
				l1.val = temp;
				l2 = l2.next;
			} else {
				int temp = l1.val + carry;
				if (temp > 9) {
					temp -= 10;
					carry = 1;
				} else {
					carry = 0;
				}
				l1.val = temp;
			}
			pre = l1;
			l1 = l1.next;
		}
		
		while (l2 != null) {
			int temp = l2.val + carry;
			if (temp > 9) {
				temp -= 10;
				carry = 1;
			} else {
				carry = 0;
			}
			l2 = l2.next;
			new ListNode(temp);			
			pre.next = new ListNode(temp);
			pre = pre.next;
		}
		
		if (1 == carry) {
			pre.next = new ListNode(1);
		}
		
		return lr;
	}
	
	public void test() {
		ListNode l1 = new ListNode(2);
		l1.next = new ListNode(4);
		l1.next.next = new ListNode(5);
		l1.next.next.next = new ListNode(8);
		
		ListNode l2 = new ListNode(5);
		l2.next = new ListNode(6);
		l2.next.next = new ListNode(4);
		l2.next.next.next = new ListNode(1);
		
		ListNode lr = addTwoNumbers(l1, l2);
		
		while (lr != null) {
			System.out.print(lr.val + " ");
			lr = lr.next;
		}	
	}

	public static void main(String[] args) {
		AddTwoNumbers atn = new AddTwoNumbers();
		atn.test();
	}

}
